import java.util.*;
public class DepthFirstSearch {
    private Map<Integer,List<Integer>> graph;
    private boolean[] visited;
    public DepthFirstSearch(Map<Integer,List<Integer>> graph) {
        this.graph = graph;
        this.visited = new boolean[graph.size()];
    }
    public void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;
        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.print(node + " ");
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }


//        public static void main(String[] args) {
//            Map<Integer, List<Integer>> graph = new HashMap<>();
//            graph.put(0, Arrays.asList(1, 2));
//            graph.put(1, Arrays.asList(3));
//            graph.put(2, Arrays.asList(3));
//            graph.put(3, Collections.emptyList());
//            graph.put(4, Arrays.asList(5));
//            graph.put(5, Collections.emptyList());
//
//            DepthFirstSearch dfs = new DepthFirstSearch(graph);
//            dfs.dfs(0); // 应输出 0 1 3 2
//        }
}

